package main

/*
   给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
   如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

   请必须使用时间复杂度为 O(log n) 的算法。

   输入: nums = [1,3,5,6,7,8,9,10], target = 5
   输出: 2
   输入: nums = [1,3,5,6], target = 7
   输出: 4
*/
func main() {

	//strsArray := []string{"a", "b", "c"}
	//str := "sssssss"

	//测试用例
	nums := []int{1, 3, 5, 6}
	target := 2

	//打印测试用例返回结果
	resp := searchInsert(nums, target)
	println(resp)

}

func searchInsert(nums []int, target int) int {
	numsLen := len(nums)
	//i := numsLen / 2
	result := binarySearch(nums, 0, numsLen-1, target)

	return result
}

func binarySearch(nums []int, start, end, target int) int {
	binary := (start + end) / 2
	if start > end {
		if end == -1 {
			return 0
		}
		if target < nums[end] {
			return end
		} else {
			return start
		}
	}
	if target < nums[binary] {
		binary = binarySearch(nums, start, binary-1, target)
	} else if target > nums[binary] {
		binary = binarySearch(nums, binary+1, end, target)
	}
	return binary
}

func noneRecursiveBinarySearch(nums []int, target int) int {
	start := 0
	end := len(nums)
	middle := (start + end) / 2
	for start <= end {
		if target == nums[middle] {
			return middle
		} else if target < nums[middle] {
			end = middle - 1
		} else {
			start = middle + 1
		}
	}
	return -1

}
